package com.atguigui.leetcode1;

/**
 * 不同路径 III
 * Project: leetcode
 * Package: com.atguigui.leetcode1
 * Version: 1.0
 * <p>
 * Created by WJX on 2023/8/4 8:45
 */
public class P980UniquePathsIii {


    class Solution {
        // 四个选择
        static int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};


        public int uniquePathsIII(int[][] grid) {
            // 矩阵的长、宽
            int r = grid.length, c = grid[0].length;
            // n为可移动的点个数
            int si = 0, sj = 0, n = 0;
            for (int i = 0; i < r; i++) {
                for (int j = 0; j < c; j++) {
                    if (grid[i][j] == 0) {  // 可移动的点
                        n++;
                    } else if (grid[i][j] == 1) {   // 起始点位置
                        n++;
                        // 找到起始点，并记录位置
                        si = i;
                        sj = j;
                    }
                }
            }

            return dfs(grid, si, sj, n);
        }

        private int dfs(int[][] grid, int si, int sj, int n) {
            // 到达目的地
            if (grid[si][sj] == 2) {
                return n == 0 ? 1 : 0;
            }
            int r = grid.length, c = grid[0].length;
            int t = grid[si][sj];
            // 将坐标设为-1，代表已经走过
            grid[si][sj] = -1;
            int res = 0;
            // 遍历四个方向
            for (int[] dir : dirs) {
                // 新的点号位置
                int ni = si + dir[0], nj = sj + dir[1];
                // 判断新的点是否符合在矩阵中
                if (ni >= 0 && ni < r && nj >= 0 && nj < c && (grid[ni][nj] == 0 || grid[ni][nj] == 2)) {
                    res += dfs(grid, ni, nj, n - 1);
                }
            }
            grid[si][sj] = t;
            return res;
        }
    }
}
